29 May 1999
Source: US Patent Office Online:
http://www.uspto.gov/
Search "National Security Agency" though none of the patents disclose the
full name.
For related images see IBM's patent server:
http://www.patents.ibm.com/ibm.html
United States Patent |
4,161,032 |
Williams |
July 10, 1979 |
Serial arithmetic functions with magnetic bubble logic elements
Abstract
Compact arrangements of two-input magnetic bubble logic gates providing bubble
devices for performing serial integer arithmetic on binary integers are
disclosed. Using only a small number of different types of logic gates, designs
are given for devices for performing serial addition, subtraction, multiplication
and division arithmetic operations on binary integers, represented as sequences
of magnetic bubbles. All logical interactions use bubble repulsion to prevent
bubbles from transferring to adjacent propagation paths via preferred
transitions. By using only two-input gates and a pipeline computational
structure, hardware design is simplified and advantage is taken of the inherent
serial nature of bubble technology. The simple gate interconnection geometry
has a minimum of feedback paths and results in devices which are not burdened
with excessive numbers of bubble generators, annihilators or crossovers.
Inventors: |
Williams; Richard P. (Columbia, MD) |
Assignee: |
The United States of America as represented
by the Director of the (Washington, DC) |
Appl. No.: |
878207 |
Filed: |
February 16, 1978 |
U.S. Class: |
364/714; 365/5 |
Intern'l Class: |
G06F 007/48; G11C 011/14 |
Field of Search: |
364/714 365/5 |
References Cited
[Referenced
By]
U.S. Patent Documents
3678287 |
Jul., 1972 |
Chow |
365/5. |
3750106 |
Jul., 1973 |
Caron |
364/900. |
3798607 |
Mar., 1974 |
Minnick et al. |
364/200. |
3894223 |
Jul., 1975 |
Majima et al. |
364/714. |
3983383 |
Sep., 1976 |
Naden |
364/714. |
3986016 |
Oct., 1976 |
Linn et al. |
364/714. |
4011461 |
Mar., 1977 |
Chang et al. |
365/5. |
Primary Examiner: Smith; Jerry
Attorney, Agent or Firm: Utermohle; John R. Young; Barry N.
Claims
1. A magnetic bubble device for performing an arithmetic operation on magnetic
bubble streams representative of binary numbers, comprising:
input means for two or more magnetic bubble streams representative of binary
numbers;
output means for at least one bubble stream representative of the result
of the arithmetic operation; and
a magnetic bubble arithmetic unit connected between said input and output
means, said arithmetic unit comprising:
a plurality of magnetic bubble elements, said plurality including a first
two-input AND-EXCLUSIVE OR bubble logic gate, said gate having first and
second continuous, uninterrupted paths extending from the input to the output
of said gate for the passage of bubbles therethrough, the outputs of said
paths representative of the logical AND operation performed on bubbles input
to said paths, and a third output path disposed between said first and second
paths for providing an output representative of the EXCLUSIVE OR operation
performed on bubbles input to said first and second paths, said gate further
having a pair of preferred transition paths from said first and second paths
to said third path such that a bubble entering on either of said first or
second paths, in the absence of a bubble entering on the other path, exits
the gate on said third path, said plurality of magnetic bubble elements
interconnected in a fixed logical pipeline configuration within said unit
for performing a predetermined arithmetic operation, said configuration
characterized by an absence of bubble feedback paths internal to said unit.
2. The device of claim 1 wherein said arithmetic unit further comprises an
incremental adder bubble logic element having a first word input and a second
one bit increment input, said word input connected to said EXCLUSIVE OR output
of said first AND-EXCLUSIVE OR gate and said one bit increment input connected
through a 1-bit delay element to said AND output of said gate, thereby providing
a serial adder for adding two binary integers input to said gate.
3. The device of claim 2 further including bubble annihilators for annihilating
unused bubble outputs from said gate.
4. The device of claim 3 further comprising second and third AND-EXCLUSIVE
OR bubble logic gates interconnected together on the inputs to said serial
adder, for providing a carry-save adder for adding three binary integers.
5. A magnetic bubble device for performing an arithmetic operation on magnetic
bubble streams representative of binary numbers, comprising:
input means for two or more magnetic bubble streams representative of binary
integers;
output means for at least one bubble stream representative of the result
of the arithmetic operation;
an airthmetic unit connected between said input and output means, said arithmetic
unit comprising a plurality of magnetic bubble elements, said elements including:
a first two-input AND-EXCLUSIVE OR bubble logic gate having first and second
inputs, and outputs representative of the logical AND and the EXCLUSIVE OR
operation on said two inputs;
an incremental adder bubble logic element having a first word input connected
to said EXCLUSIVE OR output of said first gate, and a second one bit increment
input connected through a 1-bit delay element to said AND output of said
gate, thereby providing a serial adder; and
second and third AND-EXCLUSIVE OR bubble logic gates interconnected on the
inputs to said serial adder, for providing a carry-save adder for adding
three binary numbers.
6. A magnetic bubble device for performing an arithmetic operation on magnetic
bubble streams representative of binary numbers, comprising:
input means for two or more magnetic bubble streams representative of binary
integers;
output means for at least one bubble stream representative of the result
of the arithmetic operation;
an arithmetic unit connected between said input and output means, said arithmetic
unit comprising a plurality of magnetic bubble elements, said elements including:
a first two-input AND-EXCLUSIVE OR bubble logic gate having first and second
inputs, and first and second outputs representative of the logical AND operation
and a third output representative of the EXCLUSIVE-OR operation;
a bubble replicator element having an input and first and second outputs,
said replicator input being connected to said EXCLUSIVE OR output of said
gate;
means for merging said first replicator output with said first AND output
of said gate; and
means for supplying said merged outputs to said first input of said gate,
thereby providing a continuous stream of bubbles through said gate, such
that a binary number input to said second input of said gate is output from
said second replicator output inverted with respect to said input binary
number, thereby providing an inverter.
7. The device of claim 6 further including an incremental adder connected
to the output of said inverter such that the output of said incremental adder
is the 2's complement of the binary number input to said inverter.
8. The device of claim 6 further comprising a serial adder connected to the
output of said inverter for adding said inverted binary number with a second
binary number input to said serial adder and means for supplying a sync input
to said serial adder, such that the output of said serial adder is a binary
number equal to the difference between said input binary numbers, thereby
providing a subtraction device.
9. A magnetic bubble device for performing multiplication and division arithmetic
operations on magnetic bubble streams representative of binary numbers,
comprising;
input means for two or more magnetic bubble streams;
output means for at least one bubble stream representative of a partial
arithmetic operation performed on said input bubble streams;
a magnetic bubble cellular unit connected between said input and output means,
said magnetic bubble unit comprising;
a plurality of magnetic bubble elements, said plurality including a first
group of elements configured in a fixed logical relationship to one another
for performing a predetermined logical operation on said input bubble streams,
and a second group of elements configured in a fixed logical relationship
to one another for performing a second predetermined operation on said bubble
streams, said first and second groups of elements being interconnected such
that said magnetic bubble cellular unit performs said partial arithmetic
operation, and wherein said bubble unit is further characterized in being
adapted to be interconnected in tandem with other like bubble units in a
pipeline configuration to perform said arithmetic operation.
10. The magnetic bubble device of claim 9 wherein said arithmetic operation
is multiplication of two numbers, one being a multiplier and one being a
multiplicand and wherein said first group of elements is configured for
performing a logical AND operation on said bubble streams, and said second
group of elements includes means for forming a partial product between the
numbers represented by said bubble streams.
11. The magnetic bubble device of claim 10 wherein said device further comprises:
n arithmetic cellular units connected in said pipeline, where n is the number
of bits in said numbers; and
bubble adder means for combining partial products from said cellular units
to form the product of said numbers.
12. The magnetic bubble device of claim 11 wherein said AND operation examines
individually each bit of said multiplier, and said means for forming a partial
product further comprises means for accumulating partial products and adding
said multiplicand to said accumulated partial products, when said examined
multiplier bit is a one.
13. The magnetic bubble device of claim 10, further comprising means for
spreading said multiplier and multiplicand by placing a zero between each
pair of adjacent bits, and wherein said cellular unit further comprises delay
means for successively shifting said multiplicand with respect to said multiplier
prior to said AND operation.
14. The device of claim 13 wherein said means for performing said logical
AND operation includes a plurality of AND-Invert bubble logic gates and said
combining means includes serial adders.
15. The magnetic bubble device of claim 9 wherein said arithmetic operation
is division of two numbers, one of the two numbers being a divisor and one
being a dividend, said bubble device being a divider, and wherein said first
group of elements includes means for determining the sign of said dividend
and means for complementing said divisor when said dividend is positive or
zero, and said second group of elements includes means for adding said divisor
or its complement to said dividend to provide a remainder and a partial quotient.
16. The device of claim 15 wherein said divider further includes means for
performing successive addition operations wherein said divisor or its complement
is successively added to the remainder and partial quotient resulting from
the previous addition.
17. The device of claim 16 wherein said adding means includes a serial adder.
18. The device of claim 17 wherein said means for performing said successive
addition operations includes a recursive data connection to said pipeline
such that said successive addition operations are performed by said serial
adder.
Description
BACKGROUND AND SUMMARY OF THE INVENTION
This invention relates generally to magnetic bubble devices and more particularly
to magnetic bubble devices for performing serial arithmetic operations on
binary integers and special purpose pipeline processors using the same.
Magnetic bubble technology development has primarily focused on memory
applications. Magnetic bubble technology has been shown to be capable of
yielding relatively compact LSI chips having large memory storage capability,
at relatively low cost. In some applications, bubble technology may achieve
considerable advance over semiconductor technology in chip area utilization.
Since it is feasible to make bubble chips larger than semi-conductor chips,
bubble technology permits a greater degree of integration to be achieved.
Bubble chips generally require only one critical masking step in their
fabrication process. Therefore, they are more economical to produce than
semiconductor chips. Furthermore, bubble devices operate on less power than
most comparable semiconductor devices.
Bubble technology may also be used for logic operations. A variety of useful
logic functions has been demonstrated, using the repulsive interaction between
bubbles to perform logic operations. For example, U.S. Pat. Nos. 3,731,109
to Garey, 3,743,851 to Kohara, 3,750,106 to Caron and 3,909,622 to Minnick,
disclose various bubble logic devices such as AND, NAND, OR, NOR, Exclusive-OR,
NOT and inversion. Although the principles of bubble logic have been
demonstrated, logic design exercises have produced generally pessimistic
estimates of bubble logic performance in comparison to semiconductor technology.
These unfavorable comparisons have been due to the constraints under which
magnetic bubble devices must operate and the lack of logic designs compatible
with these constraints.
One constraint on magnetic bubble technology is the relatively slow speed
of bubble propagation, currently approximately 0.5 MHz in commonly used bubble
materials. In addition, since bubbles propagate serially in shift register
fashion along propagation paths, the geometry problems associated with the
interconnection of gates and the equalization of propagation delays may be
quite significant. Although various logic schemes have been suggested to
avoid some of these difficulties, bubble logic designs, for the most part,
have been aimed at achieving a general purpose logic capability which is
obtained at the expense of globally efficient designs. For example, U.S.
Pat. No. 3,798,607 to Minnick, discloses a general purpose computer design
based upon bubble technology. This computer executes instructions slowly
and consequently its applications are very limited. It is clear from the
intrinsic characteristics of bubble technology, that arbitrary interconnections
of bubble logic gates cannot be accomplished with efficient utilization of
chip area. Nevertheless, specific applications exist where the required data
rate is matched to the bubble propagation speed and where pipeline bubble
logic designs can be implemented efficiently in terms of chip area utilization,
with minimum area devoted to gate interconnections and bubble generators
and annihilators.
The inherent serial nature of magnetic bubble technology makes it ideally
suited to a pipeline computational structure with a minimum of internal feedback.
Assuming a 0.5 MHz bubble propagation rate, 16-bit words, and one propagation
period per bit, the throughput of a pipeline processor utilizing bubble
technology could be 30,000 words per second, which represents a capability
of processing signals of 15 KHz bandwidth. This speed is adequate for many
applications. For example, the speed required for voice processing is well
within the capability of existing bubble technology.
It is desirable therefore and an object of the invention in its most general
sense, to provide pipeline designs for serial arithmetic bubble devices which
will take maximum advantage of the characteristics of magnetic bubble technology
and which will form the basis for the designs of special purpose processors,
for applications which lend themselves to pipeline processing.
Accordingly, an approach to the design of serial arithmetic devices has been
developed using principles which are intended to facilitate the hardware
design and to achieve maximum use of chip area. The same type of bubble
interaction, i.e., bubble repulsion to prevent bubble transfer, is used in
all gates so that their design will be similar. Furthermore, only two-input
gates are used since these structures are the simplest and require the least
development effort. Although three-input gates may be used, they are more
complicated and are not essential for achieving a reasonably compact design.
My designs for serial arithmetic elements demonstrate that serial arithmetic
can be performed by a compact arrangement of a small number of different
types of basic bubble logic gates. These basic circuits are not burdened
with excessive numbers of bubble generators, annihilators, or crossovers,
and no problem is encountered with fan out. Furthermore, by using only two-input
gates and a pipeline computational structure, the geometry of the circuits
is significantly simplified. This facilitates the hardware design and permits
reasonably high computing power to chip area ratios to be achieved. Consequently,
special purpose pipeline bubble logic processors utilizing these designs
can be made to compare favorably with conventional semiconductor logic designs.
To facilitate an understanding of the invention, it is helpful to define
certain terminology used herein. The term "element" refers to the various
two-input bubble logic gates and components illustrated in FIGS. 1 and 2,
and the incremental adder of FIG. 3A which form the basic building blocks
for implementing circuits which perform arithmetic operations. A "unit" is
an interconnection of elements which performs some function, such as an
arithmetic operation. The term "device" refers generically to an interconnection
of units or elements. The term "pipeline" refers to the structure of a device
in which the geometry of its units is such that processing operations are
sequentially performed on a continuous flow of serial data through the units,
without data feedback paths internal to the units.
A magnetic bubble device for performing serial integer arithmetic on binary
integers which provides the aforementioned and other advantages may include
input means for two magnetic bubble streams that are representative of two
binary integers upon which the arithmetic operation is to be performed, output
means for outputting a magnetic bubble stream which is representative of
the result of the arithmetic operation and an arithmetic unit comprising
a plurality of magnetic bubble elements, including at least a first two-input
bubble logic gate for performing a logical operation on two binary integers
input to the gate, the elements being interconnected in a predetermined pipeline
configuration between the input and output means, for performing a predetermined
arithmetic operation on the binary integers.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 comprising FIGS. 1A-1D illustrates the basic two-input logic gates
which are utilized as building blocks for implementing serial arithmetic
function devices.
FIG. 2 comprising FIGS. 2A-2D illustrates additional components necessary
for implementing the serial arithmetic functions.
FIG. 3 comprising FIGS. 3A-3B illustrates an incremental adder and a serial
adder for performing serial addition.
FIG. 4 illustrates a carry-save adding technique, which performs addition
of three inputs without recirculating carries.
FIG. 5 comprising FIGS. 5A-5C illustrates an inverter circuit, a 2's complement
circuit and a subtraction device for implementing serial subtration.
FIG. 6 illustrates one embodiment of a pipeline multiplication cell for
multiplying non-negative numbers.
FIG. 7 illustrates a second embodiment of a pipeline multiplication cell.
FIG. 8 illustrates a 2's complement multiplier.
FIG. 9 comprising FIGS. 9A and 9B illustrates the operation and a pipeline
logic design for a non-restoring division cell.
FIG. 10 illustrates a pipeline division circuit having a recursive connection.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENT
The basic two-input gates utilized as building blocks for constructing serial
arithmetic function devices are illustrated in FIG. 1. The symbolism employed
corresponds closely to actual gate construction. The convention is adopted
that data flow is from left to right unless an arrow indicates otherwise.
Logic is accomplished by introducing a preferred transition between two parallel
propagation paths. An input bubble, in the absence of a second input bubble
on a parallel path, will transfer from one path to the other in the direction
indicated by the arrow. When two bubbles enter simultaneously on parallel
paths, the mutual repulsion between them prevents the transfer and both bubbles
continue to propagate along the path on which they are entered.
FIG. 1A illustrates an AND-INVERT (AI) gate. As illustrated, there is a preferred
transition path for a bubble input at A to output path AB. If two bubbles
are simultaneously input on paths A and B, they will propagate through the
gate with the input bubble on path A appearing at output AB and the input
bubble at path B appearing at output B. The presence of the bubble on path
B prevents the bubble at input A from making the preferred transition to
output AB. If a bubble is input on path A only, it will make the preferred
transition and appear on output path AB. A bubble input on path B will always
appear at output B, since there is no transition path provided in the gate.
Consequently, output AB is the AND output of the gate and output AB is the
AND-INVERT output. Input B controls the gate operation.
FIG. 1B illustrates an AND-OR (AOR) gate. For a bubble input on path A, there
is a preferred transition to OR output A+B. If bubbles are simultaneously
input on inputs A and B, repulsion between the two bubbles will prevent the
bubble on path A from making the preferred transition and it will appear
at AND output AB. In any case, a bubble input on path B will appear on output
A+B.
FIG. 1C illustrates an AND-EXCLUSIVE OR (AXO) gate. As illustrated, preferred
transitions exist between both input paths A and B and output path A.sym.B.
This output represents the modulo 2 addition (exclusive-OR function) of the
two inputs. A bubble input on either path A alone or path B alone will appear
at this output. Bubbles simultaneously entered on path A and B will prevent
the transition of either bubble to the exclusive-OR output and each will
propagate through the gate and appear on its respective AND output, AB.
FIG. 1D illustrates a Crossover (CO) gate. This gate operates with a resident
bubble. Crossover of two parallel paths is accomplished by trapping a bubble
in an idling position between the paths. With no input, this bubble oscillates
between the two paths in a manner similar to the transfer action in the logic
gates. A bubble from either input approaches the idling bubbles when it is
near the opposite propagation path. The repulsion forces the idling bubble
to exit on the opposite path (crossover action) and the incoming bubble becomes
trapped in the idler. When two bubbles enter, they do not approach the idler
simultaneously, due to a phase difference (1/2 period delay) which is provided
between the two input paths. In this case, the first input bubble interacts
with the idling bubble as described above, but the second input arrives before
the first bubble can become trapped. Repulsion between the first and second
bubbles forces the first bubble to remain on its propagation path and it
exits the crossover gate. The second bubble then becomes trapped in the idler.
The gates illustrated in FIGS. 1A-1C may be implemented with designs given
in the previously cited references to Garey, Kohara, Caron and Minnick. A
suitable design for the crossover gate of FIG. 1D is given in U.S. Pat. No.
3,543,255 to Morrow.
Other elements necessary for implementing serial arithmetic devices are the
components illustrated in FIG. 2. The replicator of FIG. 2A uses the field
from propagation patterns to stretch and split bubbles. A suitable design
is given in U.S. Pat. No. 3,868,661 to Bonyhard. The annihilator of FIG.
2B collapses bubbles by trapping them near an unfavorable magnetic pole.
A suitable design is illustrated in U.S. Pat. No. 3,701,125 to Chang. The
n-bit delay of FIG. 2C is achieved with a folded propagation path having
a length necessary for the required delay, and the exclusive merge of FIG.
2D is a simple junction of two propagation paths which logically can not
have bubbles in equivalent positions.
Addition
Binary integer representation is assumed with the presence or absence of
a bubble representing 1 or 0, respectively. Numbers move serially along
propagation paths, least significant bit first. One number is left shifted
with respect to another by propagating it through delay. A right shift is
accomplished by delaying the other path. Since all propagation paths represent
delay, the delays shown explicitly in the figures are relative to the other
paths. Only those delays are shown which represent a signficant feature of
the algorithm or which are important for circuit design considerations.
FIG. 3A illustrates an incremental adder, formed by returning one AND output
of the AXO gate illustrated in FIG. 1C to its corresponding input, to form
a closed carry loop, represented by circle 10, with a delay of one bit interval.
This device functions as an incremental adder because it will add 1 bit to
a number if a solitary input bubble enters the one bit increment input to
the carry loop 10. The carry is propagated (delayed) by remaining in the
loop until it falls into a vacant position in the input word. All carries
produced by the addition operation exit from the carry output. The incremental
adder of FIG. 3A is useful in forming the 2's complement and is valuable
as a control element. In the latter case, the word input is a stream of bubbles
with at least one vacancy occuring at the word interval. A bubble supplied
to the carry loop will divert the bubble stream from the sum output to the
carry output, until a vacancy arrives to empty the loop.
Combining the incremental adder of FIG. 3A with a half adder (AXO gate),
11, forms a true serial adder as illustrated in FIG. 3B. The two numbers
to be added are input to AXO gate 11. The exclusive-OR output of AXO gate
11 is fed to the word input of incremental adder 12. One AND output of AXO
gate 11 is connected to annihilator 14. The second AND output of AXO gate
11 is connected to the 1-bit increment input of incremental adder 12 through
a 1-bit delay 16. The carry output of incremental adder 12 is fed to annihilator
18 and the sum of the two inputs appears at the sum output. Carries are produced
in advance by AXO gate 11 and are routed to the carry loop of incremental
adder 12. Bubbles entering this loop can not encounter a previous carry since
the generation of a carry creates a vacant position in the word that arrives
first and empties the loop.
FIG. 4 illustrates a carry-save technique to perform multiple additions.
Three numbers are combined by two half adders, AXO gates 20 and 22. The carry
outputs of these gates can be merged in exclusive merge 24, since the addition
of three numbers can at most produce one carry at each bit position. The
combined carry output is then delayed by 1-bit delay 26, to achieve alignment
for subsequent addition. The sum and carry outputs of the carry-save stage
comprising gates 20 and 22, exclusive merge 24 and 1-bit delay 26, can be
routed to other carry-save stages or the final sum can be computed with a
serial adder, 28, as illustrated. The carry-save scheme illustrated in FIG.
4 can add many numbers with only one carry-propagating adder being required.
This technique has the potential for conserving chip area since carry delay
loops are not used.
Subtraction
Subtraction may be accomplished by forming the 2's complement and adding.
The 2's complement can be generated conveniently by forming the logical inverse
and adding 1. Inversion may be accomplished, for example, by supplying a
continuous stream of bubbles (logical 1) to one input of either an AI gate
or an AXO gate. However this requires a bubble generator to provide the
continuous stream of bubbles. A self-contained inverter, not requiring a
bubble generator, is illustrated in FIG. 5A. The exclusive-OR (inverted output)
of an AXO gate is replicated with replicator 30, merged with one of the gate's
AND outputs, using an exclusive merge 32, and fed back to the 1 input of
the gate corresponding to that AND output. This feedback loop provides a
continuous stream of bubbles in the gate, which are used to invert an input
at B. The circuit is self-initializing, since any vacant positions in the
recirculating path formed by the feedback, will eventually be filled from
the input. The inverted output is taken from replicator 30. An uninverted
output also appears at the second AND output of the gate, which may be
annihilated if not needed.
FIG. 5B illustrates one method of generating the 2's complement, using the
inverter of FIG. 5A and an incremental adder, 34. An input is inverted in
inverter 33 and supplied to the word input of incremental adder 34. A sync
input, consisting of a single bubble synchronized with the beginning of each
word, is supplied to the 1-bit increment input of adder 34. The sum output
of adder 34 is the 2's complement of the input. This 2's complement may be
combined with a second input in a serial adder to provide subtraction. It
is assumed that sync bubbles are available and can be routed to any location
with sufficient delay to give proper timing. if a zero input is complemented
or if signed numbers are added, there must be a high-order vacant position
in each word to accommodate an overflow bubble and provision must be made
for removing or ignoring overflows.
When one number is added to the complement of another number, a separate
incrementing adder is not needed to form the complement. In this case, the
sync may be supplied directly to the carry loop of the serial adder. An efficient
subtraction device may be implemented as shown in FIG. 5C, by the addition
to the 2's complement circuit of FIG. 5B an AXO gate, 35, a 1-bit delay,
36, and an exclusive merge, 37, for supplying the sync bit to the incremental
adder, 34. Incremental adder 34, AXO gate 35 and 1-bit delay 36 form a serial
adder. Inverter 33 inverts the subtrahend at input 1 and the result is added
to the minuend at input 2 by the serial adder. The 2's complement is completed
by supplying the sync bit to the carry loop of incremental adder 34, via
the exclusive merge 37.
Multiplication
FIG. 6 illustrates one cell of an embodiment of a pipeline multiplier. In
the illustrated embodiment, each such cell adds the shifted multiplicand
if the corresponding multiplier bit is 1. An n-bit multiplier word requires
n multiplication cells. The pipeline multiplier illustrated in FIG. 6 will
multiply positive or zero numbers. Signed numbers must be converted to magnitudes
with the sign of the product determined in advance. It is convenient to place
the product sign bit in the product propagation path prior to multiplication.
Both multiplier and multiplicand are n-bit words with at least n+1 high-order
zeros to allow space for the full precision and sign of the product.
The multiplier enters the first cell with its most significant bit aligned
on the least significant bit of the multiplicand. The multiplier enters AI
gate 38 along with a sync bubble. The sync bubble picks off a multiplier
bit, beginning in the first cell with the most significant position. This
multiplier bit enters the incremental adder 39 where it diverts a stream
of n bubbles also entering adder 39, through AI gate 40. The multiplicand
enters the second input of AI gate 40. The bubble stream causes the multiplicand
to be replicated in replicator 42, into a carry-save adder comprising gates
44 and 46. A serial adder could be used in place of the carry-save adder,
if desired. The multiplicand is further transmitted to the next cell, either
from the output of replicator 42 or from the invert output of AI gate 40,
via exclusive merge 48. The sum and carry outputs of AXO gate 46 of the serial
adder are output as a partial product to the next cell, via 1-bit delay 50
and 2-bit delay 52. These delays left-shift the partial product by 1-bit
with respect to the multiplicand. The 1-bit delay 54 on the invert output
of AI gate 38 aligns the next most significant multiplier bubble's position
with the sync bubble, prior to input to the next cell. High-order vacancies
following the n-bubble stream carry away the used multiplier bubbles.
Gates 44 and 46 of the carry-save adder can be eliminated, if desired, from
the first multiplication cell since there is no partial product at that point.
In this case the output of replicator 42 would be fed to the second cell
through a 1-bit delay. Similarly, only one AXO gate, 46, would be required
in the second cell to accept this input. Thereafter, subsequent cells would
require both gates 44 and 46. Subsequent to the final multiplication cell,
the two partial products are combined by a serial adder to produce the result.
The multiplication cell of FIG. 6 has the capability of clamping or holding
the multiplier in place if the n-bubble input is replaced by a continuous
stream of bubbles. A sequence of n-vacancies will release the multiplier.
An alternative embodiment of a pipeline multiplier for positive numbers is
illustrated in FIG. 7. Although FIG. 7 illustrates an embodiment using bubble
logic, the algorithms embodied in the implementation and to be described
hereinafter, may be implemented in CCD's or conventional semiconductor devices.
Although the illustrated multiplier operates only with positive numbers,
modifications could be made to allow multiplication of 2's complement numbers.
Conventional multiplication is done by examining individually each bit of
the multiplier word and adding the shifted multiplicand if the multiplier
bit is a one. The multiplication scheme illustrated in FIG. 7 does not look
at individual multiplier bits. It generates partial products by performing
the logical AND operation between the multiplicand and multiplier, for each
of 2n-1 positions, obtained by shifting the multiplicand with respect to
the multiplier. Both multiplier and multiplicand must be in a "spread" format,
which is generated by placing a zero between each pair of adjacent bits.
Thus an n-bit word is spread to occupy 2n bit positions. Adjacent words in
the data streams must be separated by 2n vacant positions.
Processing begins with the least significant bit of the multiplier aligned
with respect to the most significant bit of the multiplicand or vice versa.
The multiplier and multiplicand are input to AI gate 56 and a logical AND
operation is performed. The result is a partial product which contains either
even bits only or odd bits only with respect to the final product. The multiplier
which was input to AI gate 56 on input A is recovered by merging one output
of replicator 61 with the invert output of AI gate 56. The recovered multiplier
is then input to AI gate 60. The multiplicand, which was input to AI gate
56 on input B, is left-shifted 2 bits by a 2-bit delay 58 and a second AND
operation is performed by AI gate 60, on the multiplicand and the multiplier.
This produces a partial product complementary to the previous product, i.e.,
even bits instead of odd, or vice versa. The first partial product from
replicator 61 is left-shifted one bit by 1-bit delay 62, to give it the proper
numerical value and it is merged with the second partial product from replicator
63. The even-odd bit arrangement permits the combination of the data streams
by the simple merge. The multiplicand is again left-shifted by 2-bit delay
64. The left-shifted multiplicand, the multiplier and the partial product
from replicator 63 are then fed to the next multiplication cell.
In the next cell, the process is repeated with AND operations performed by
AI gates 66 and 68. The process continues until 2n-1 partial products have
been generated. The partial products from each cell are merged in pairs and
the resulting data streams are combined in adders. For example, the partial
products from the first and second cell are combined in serial adder 70.
It is also possible to use the carry-save adding scheme. Since the number
of partial products is odd, the final partial product is not paired. It must
be added to the accumulated partial products by a separate serial adder 72.
However since the final partial product consists of only one bit, this adder
may be an incrementing adder. The output of adder 72 is the desired product.
When the multiplication scheme of FIG. 7 is used to square a number, the
symmetry of the operations allows the square to be produced after only n
partial products have been generated. The scheme for squaring is the same
as previously described, however the operation is terminated after the nth
partial product is produced. Prior to adding the nth partial product, the
accummulated partial product is doubled, i.e., left-shifted, to account for
the symmetric part of the process which was omitted. If the squaring operation
is begun with the operands in the maximum overlap position, the high-order
portion of the square will be generated first and the operation may be truncated
at any step short of completion to produce an approximate result.
FIG. 8 illustrates a 2's complement multiplier in which both the multiplier
and the multiplicand may be in 2's complement form. There are four conditions
which must be satisfied when 2's complement numbers are multiplied and which
cause this circuit to be different from a positive number multiplier. First,
when a negative multiplicand is right-shifted, it sign bit must be extended
(repeated) on the left in the high-order position. Secondly, in order to
match the length of the multiplicand, the 1's stream must also be extended
on the left in each cell. Third, when the multiplier is negative, the result
of performing multiplication with a 2's complement multiplier is the product
(2.sup.N -A)B, where A is the absolute value of the multiplier and B is the
multiplicand. The correct result is therefore obtained by subtracting 2.sup.N
B. This is done by first generating the complement of 2.sup.N B in the first
cell if the multiplier is negative. Fourth, the addition of 2's complement
numbers can produce an overflow at each cell and all overflow bubbles must
be removed to keep the length of the product within prescribed bounds.
The multiplicand is assumed to have either n high-order zeros or n high-order
ones. Thus, the bubbles necessary for satisfying the first condition are
carried along with the multiplicand if it is negative. By satisfying the
second condition, the extended 1's stream automatically deflects the proper
number of bubbles from the multiplicand to meet the first condition. The
first cell of the 2's complement multiplier of FIG. 8 is a modified version
of the general cell used in the remainder of the circuit. It generates the
number -2.sup.N B if the multiplier is negative.
Referring to FIG. 8, in the first cell the sync bit picks off the multiplier
sign bit in AI gate 74 and sends the bit to incremental adder 76. This bit
deflects a 1's stream of bubbles entered at the word input of adder 76 into
the carry output of adder 76 and thus through AI gate 78. This causes the
multiplicand, which is input into AI gate 78, to be diverted into replicator
80, which feeds an inverter 82. The multiplicand is thus inverted and supplied
to the second cell of the multiplier through a 1-bit delay 84. In the second
cell, the inverted multiplicand is input to AXO gate 86 along with a sync
bit supplied from replicator 95 through n-bit delay 89. The sync bit causes
a 1 to be added to the inverted multiplicand in AXO gate 86 to complete the
formation of the 2's complement.
The sync bit supplied with the multiplier to AI gate 74, passes through the
gate to replicator 87 where it is replicated and passed to crossover gate
88 and into the carry loop of incremental adder 90. If the 1's stream has
not been diverted in incremental adder 76, the sync bit will remain in the
carry loop until if falls into the first vacancy following the 1's stream.
Thus the 1's stream is extended on the left by one bit as required by the
second condition. If the 1's stream is deflected in adder 76, the multiplier
bit will provide the required extension and the sync bit transmitted to adder
90 will pass through AOR gate 92 and be annihilated. Removal of any overflow
bit to satisfy the fourth condition, is accomplished in AI gate 94 by a sync
bubble from replicator 95.
The remainder of the circuit operates as previously described for multiplying
positive numbers. Gates 86 and 96 constitute a carry-save adder which adds
the shifted multiplicand to the accummulated partial product, if the
corresponding multiplier bit is a 1. After the final multiplication cell,
the two partial product streams must be added in a serial adder to generate
the final product.
The delays shown in FIG. 8 correspond to a bubble data format in which there
are 2n bits per word, including a position for a single over-flow bit. The
basic single precision word is n-bits long, which includes a high-order sign
bit. It is to be understood that the delays may be adjusted to provide proper
alignment and synchronization for other data formats.
Division
A pipeline bubble divider may be implemented using a non-restoring division
technique. FIG. 9A is a block diagram illustration of a representative cell
of such a divider. For n-bit words, a chain of n such cells in tandem are
required. A positive divisor is assumed but the dividend and quotient may
be in 2's complement form. The quotient is not collected separately but is
generated automatically by overflows which occur when a non-negative remainder
is produced. A series of successive add or subtract operations reduces the
magnitude of the remainder. If the remainder sign bit is removed prior to
addition, there will be a vacant position for an overflow (quotient) bit,
and a quotient will form in the space formally occupied by the high-order
portion of the remainder.
The divisor, dividend and quotient are assumed to be n-bit signed integers,
but the dividend has n high-order zeros or n high-orders ones. Referring
to FIG. 9A the divisor and dividend enter the first cell with the divisor
aligned on the n high-order bits of the dividend. In subsequent cells, the
dividend input is replaced by the remainder and a partial quotient. The divisor
is delayed by n-1 bits so that the unit bit is aligned with the sign bit
of the remainder input. This sign bit is removed and used to control a
complementing circuit. If the remainder is positive or zero, the divisor
is complemented. The remainder is then delayed by n-1 bits to realign it
with the divisor. An additional 1-bit delay (for a total delay of n-bits)
positions the remainder and divisor (or its complement) for addition. The
result of the addition is a new remainder and a quotient bit, which is input
to the next cell with the divisor, appropriately delayed, where the process
is repeated.
The detailed structure of a pipeline bubble division cell is shown in FIG.
9B. The remainder and partial quotient from a preceding cell enter the division
cell along with a sync bit via AXO gate 100. The sync bit inverts the remainder
sign bit in gate 100. This inverted sign bit is removed in AI gate 102,
replicated and fed to incremental adder 104 to control a stream of n bubbles
input to the word input of adder 104. This stream of bubbles exits the carry
output of adder 104, is replicated and enters one input of AXO gate 106.
The other input to AXO gate 106 is the divisor, which is inverted in gate
106 by the stream of bubbles. After the stream of n bubbles have passed through
adder 104, the inverted sign bubble leaves the carry loop and enters AI gate
108, where it is diverted into an annihilator 110, by the last bubble of
the n-bubble stream which has been delayed 1-bit by delay 107. The invert
output of gate 108 is delayed by 1-bit delay 112 to match the 1-bit delay
produced by delay 107 and is merged with the AND output to yield a single
path for the n-bubble stream. The divisor from AXO gate 106 and the n-bubble
stream enter AOR gate 114, which functions as a crossover since one input
is all 1's. The divisor or its inverse is output from the AND output of AOR
gate 114 and input into a serial adder comprised of AXO gate 116 and incremental
adder 118. The remainder is also input into the serial adder and is added
to the divisor or its inverse. The inverted sign is inserted into the carry
loop of incremental adder 118 to complete formation of the 2's complement.
The output from the serial adder is the new remainder and quotient, which
is input to the next division cell, along with the divisor, sync and stream
of bubbles, where the process is repeated.
The delays shown in FIG. 9A are incorporated in FIG. 9B with corresponding
delays of the n-bubble stream and the sync. There are several design options
for avoiding long delays other than those required for the divisor and the
remainder. One possibility is to invert the n-bubble stream at each cell,
since it contains high-order zeros. If the sync is derived from this inverted
stream, the sync will also be delayed. Apart from the delays required for
the divisor and the remainder, the division cell of FIG. 9B requires relatively
long propagation paths to connect cells and to connect gates within the cell.
If a reduced throughput can be tolerated, it is attractive to perform division
recursively.
A recursive division circuit is illustrated in FIG. 10. Logic is similar
to the divider of FIG. 9, but a recursive connection is made to the pipeline
so that the remainder and quotient circulate in a closed path. The circulating
remainder from crossover gate 121, enters AI gate 120 where the sync produces
a copy of the sign bit and its inverse. The inverted sign bit is used in
incremental adder 122 to control inversion of the divisor by AXO gate 124.
A serial adder composed of AXO gate 126 and incremental adder 128, combines
the divisor or its inverse with a delayed remainder from AI gate 130 and
inverted sign to form a new remainder and a quotient bit. Prior to addition,
the remainder is aligned with the divisor via a delay path which passes through
crossover gate 121 and AI gate 130, where the sign bit is removed.
It is assumed that the divisor, n-bubble stream, and sync are supplied repeatedly
at the word interval with proper timing. Means for removing the remainder
and quotient and inserting a new dividend are not illustrated. The remainder
and quotient may be removed, however, by inserting at the output of the serial
adder, an AI gate with a 2n-bubble control input. A new dividend may be input
using an exclusive merge on the path from the serial adder to AI gate 120.
A fundamental problem with recursive division is that the delay necessary
to align the remainder and the divisor consumes a large portion of the closed
path for the quotient and the remainder. For a fixed word interval (division
cycle time), the gates for complementing and adding must be constructed in
a limited path length. The configuration of the circuit of FIG. 10 has been
chosen to minimize propagation time through most of the logic and to return
the new remainder to AI gate 120 with minimum delay. Removal of the remainder
sign bit occurs on a less critical path. As should be obvious from the above,
multiplication may likewise be performed using a circuit similiar to that
of FIG. 10, having a recursive connection to the pipeline.
While the foregoing has been with reference to specific embodiments for
implementing serial integer arithmetic with magnetic bubble logic elements,
it will be appreciated by those skilled in the art, that numerous changes
may be made without departing from the spirit and the principles of the
invention. For example, a multiplexed data format wherein N data streams
have been interleaved bit by bit, may also be processed in any of the arithmetic
devices disclosed. In this case, all delays and carry loop lengths must be
increased by a factor of N, the sync bits replaced by N successive bits and
the 1's streams lengthened by a factor of N. It is intended that the invention
be limited only by the appended claims.
* * * * *